package LanQiao._15JavaB;

import java.sql.SQLOutput;
import java.util.ArrayList;
import java.util.Scanner;

//超时
public class _2 {

    static int N = 8111200;


    public static void main(String[] args) {
        int max = 197;
//925993
        for (int i = N; i > 197; i--) {
            int[] a = new int[N+1];
            int[] p = new int[N+1];
            boolean helper = helper(a, p, i);
            if (helper) {
                System.out.println(i);
                break;
            }
        }
    }

    public static boolean helper(int[] a, int[] pred, int num) {
        String string = Integer.toString(num);
        char[] charArray = string.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            int t = charArray[i] - '0';
            a[i + 1] = t;
            pred[i + 1] = a[i + 1] + pred[i];
        }
        int index = charArray.length + 1;
        int temp = a[index - 1];
        int i1 = index - 1;
        int i2 = 0;
        while (temp < num) {
            int t = pred[i1] - pred[i2];
            a[index] = t;
            pred[index] = a[index] + pred[index - 1];

            i1++;
            i2++;
            index++;
            temp = t;
        }
        return temp == num;
    }
}

//他解:
class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long an = 0;
        for (int i = 197; i < 1e7; i++) {
            if (pd(i)) {
                an = i;
            }
        }
        System.out.println(an);
    }

    private static boolean pd(int i) {
        ArrayList<Integer> ans = new ArrayList<>();
        String s = "" + i;
        int anss = 0;
        //转换为这个string方便获取每一个数位上面的证书
        for (int j = 0; j < s.length(); j++) {
            //下面的这个ans就是我们的列表容器
            ans.add(s.charAt(j) - '0');
            anss = anss + s.charAt(j) - '0';
        }
        //上面的这个循环究竟是在干什么事情：下面的这个以1234为例子说明，方便理解
        //列表 ans 存储了整数 1234 的各个数位数字 [1, 2, 3, 4]，
        // 变量 anss 的值为 10，即整数 1234 各个数位数字的总和。

        ans.add(anss);
        //这个时候i的数组元素就是ans[1,2,3,4,10]
        while (true) {
            //规律:最后一个数乘2然后减去此时的第一个数
            //乘以2减去这个里面的第一个元素就是这个类斐波那契数列的规律，避免使用纯粹的数学方法计算
            anss = (anss * 2) - ans.get(0);
            ans.remove(0);
            ans.add(anss);
            if (anss == i) {
                return true;
            } else if (anss > i) {
                return false;
            }
        }
    }
}
